{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Problem 4-1\n",
    "class Empty(Exception):\n",
    "    pass\n",
    "class ArrayStack(object): \n",
    "    def __init__(self):\n",
    "        self._data = []\n",
    "    def __len__(self):\n",
    "        return len(self._data)\n",
    "    def is_empty(self):\n",
    "        return len(self._data)==0\n",
    "    def push(self,e):\n",
    "        self._data.append(e)\n",
    "    def top(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Stack is empty')\n",
    "        return self._data[-1]\n",
    "    def pop(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Stack is empty')\n",
    "        return self._data.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3]\n",
      "[3, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "from array_stack import ArrayStack\n",
    "def reverse_data(L):\n",
    "    tmp = ArrayStack()\n",
    "    for e in L:\n",
    "        tmp.push(e)\n",
    "    return [tmp.pop() for e in L]\n",
    "\n",
    "if __name__=='__main__':\n",
    "    L=[1,2,3]\n",
    "    print(L)\n",
    "    print(reverse_data(L))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 2, 3], 'abc', 5]\n",
      "['abc', 5]\n"
     ]
    }
   ],
   "source": [
    "class LinkedStack(object):\n",
    "    class _Node(object):\n",
    "        __slots__ = '_elem', '_next'\n",
    "        def __init__(self, elem, next):\n",
    "            self._elem = elem \n",
    "            self._next = next\n",
    "    def __init__(self): \n",
    "        self._head = None\n",
    "        self._size = 0\n",
    "class LinkedStack:\n",
    "    class _Node:\n",
    "        __slots__ = '_elem','_next'\n",
    "        def __init__(self,elem,next):\n",
    "            self._elem = elem\n",
    "            self._next = next\n",
    "    def __init__(self):\n",
    "        self._head = None\n",
    "        self._size = 0\n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "    def push(self,e):\n",
    "        node = self._Node(e,self._head)\n",
    "        self._head = node\n",
    "        self._size +=1\n",
    "    def top(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Stack is empty')\n",
    "        return self._head._elem\n",
    "    def pop(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Stack is empty')\n",
    "        answer = self._head._elem\n",
    "        self._head = self._head._next\n",
    "        self._size -=1\n",
    "        return answer\n",
    "    \n",
    "    def __repr__(self):\n",
    "        data =[]\n",
    "        walk = self._head\n",
    "        while walk._next is not None:\n",
    "            data.append(walk._elem)\n",
    "            walk = walk._next\n",
    "        data.append(walk._elem)\n",
    "        return f'{data}'\n",
    "\n",
    "if __name__ =='__main__':\n",
    "    s=LinkedStack()\n",
    "    s.push(5)\n",
    "    s.push('abc')\n",
    "    s.push([1,2,3])\n",
    "    print(s)\n",
    "    \n",
    "    s.pop()\n",
    "    print(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 2, 3], 'abc', 5]\n",
      "s:[[1, 2, 3], 'abc', 5]\n",
      "t:[5, 'abc', [1, 2, 3]]\n"
     ]
    }
   ],
   "source": [
    "from linked_stack import LinkedStack\n",
    "def transfer(s,t):\n",
    "    while not s.is_empty():\n",
    "        t.push(s.pop())\n",
    "if __name__ =='__main__':\n",
    "    s=LinkedStack()\n",
    "    s.push(5)\n",
    "    s.push('abc')\n",
    "    s.push([1,2,3])\n",
    "    print(s)\n",
    "    t=LinkedStack()\n",
    "    print(f's:{s}')\n",
    "    transfer(s,t)\n",
    "    print(f't:{t}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[None, None, 3, 4, 5]\n",
      "[6, 7, 3, 4, 5]\n",
      "[3, 4, 5, 6, 7, 8, None, None, None, None]\n"
     ]
    }
   ],
   "source": [
    "#Problem 4-2\n",
    "class ArrayQueue(object):\n",
    "    DEFAULT_CAPACITY = 5\n",
    "    def __init__(self):\n",
    "        self._data = [None] * ArrayQueue.DEFAULT_CAPACITY\n",
    "        self._size = 0\n",
    "        self._front = 0\n",
    "        \n",
    "    def __len__(self) :\n",
    "        return self._size\n",
    "    \n",
    "    def is_empty(self) :\n",
    "        return self._size == 0\n",
    "    \n",
    "    def first(self) :\n",
    "        if self.is_empty() :\n",
    "            raise Empty('Queue is empty')\n",
    "        return self._data[self._front]\n",
    "    \n",
    "    def dequeue(self) :\n",
    "        if self.is_empty() :\n",
    "            raise Empty('Queue is empty')\n",
    "        result = self._data[self._front]\n",
    "        self._data[self._front]=None\n",
    "        self._front = (self._front + 1) % len(self._data)\n",
    "        self._size -= 1\n",
    "        return result\n",
    "    \n",
    "    def enqueue(self,e) :\n",
    "        if self._size == len(self._data) :\n",
    "            self._resize(2 * len(self._data))\n",
    "        avail = ( self._front + self._size ) % len(self._data)\n",
    "        self._data[avail] = e\n",
    "        self._size += 1\n",
    "        \n",
    "    def _resize(self,cap) :\n",
    "        old = self._data\n",
    "        self._data = [None] * cap\n",
    "        walk = self._front\n",
    "        for k in range(self._size) :\n",
    "            self._data[k] = old[walk]\n",
    "            walk = (1 + walk ) % len(old)\n",
    "        self._front = 0\n",
    "\n",
    "    def __repr__(self) :\n",
    "        data = []\n",
    "        walk = self._front\n",
    "        for k in range(self._size) :\n",
    "            data.append(self._data[walk])\n",
    "            walk = (1 + walk ) % len(self._data)\n",
    "        return f'{ data }'\n",
    "\n",
    "if __name__ =='__main__':\n",
    "    Q = ArrayQueue ()\n",
    "    Q.enqueue(1)\n",
    "    Q.enqueue(2)\n",
    "    Q.enqueue(3)\n",
    "    Q.enqueue(4)\n",
    "    Q.enqueue(5)\n",
    "    Q.dequeue()\n",
    "    Q.dequeue()\n",
    "    print(Q._data)\n",
    "    Q.enqueue(6)\n",
    "    Q.enqueue(7)\n",
    "    print(Q._data)\n",
    "    Q.enqueue(8)\n",
    "    print(Q._data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedQueue(object):\n",
    "    class _Node(object):\n",
    "        __slots__= '_elem','_next'\n",
    "        def __init__(self,elem,next):\n",
    "            self._elem=elem\n",
    "            self._next=next\n",
    "    def __init__(self):\n",
    "        self._head=None\n",
    "        self._tail=None\n",
    "        self._size=0\n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    def is_empty(self):\n",
    "        return self._size ==0\n",
    "    def first(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty(\"Queue is empty\")\n",
    "        return self._head._elem\n",
    "    \n",
    "    def enqueue(self,e):\n",
    "        new=self._Node(e,None)\n",
    "        if self.is_empty():\n",
    "            self._head=new\n",
    "        else:\n",
    "            self._tail._next=new\n",
    "        self._tail=new\n",
    "        self._size+=1\n",
    "\n",
    "    def dequeue(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty(\"Queue is empty\")\n",
    "        answer=self._head._elem\n",
    "        self._head=self._head._next\n",
    "        self._size-=1\n",
    "        if self.is_empty():\n",
    "            self._tail=None\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Problem 4-3\n",
    "class DoublyLinkedBase(object):\n",
    "    class _Node(object):\n",
    "        __slots__ = '_elem', '_prev', '_next'\n",
    "        def __init__(self, elem, prev, next):\n",
    "            self._elem = elem\n",
    "            self._prev = prev \n",
    "            self._next = next \n",
    "            \n",
    "    def __init__(self):\n",
    "        self._header=self._Node(None,None,None)\n",
    "        self._trailer=self._Node(None,None,None)\n",
    "        self._header._next=self._trailer\n",
    "        self._trailer._prev=self._header\n",
    "        self._size=0\n",
    "        \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._size==0\n",
    "    \n",
    "    def _insert_between(self,e,pred,succ):\n",
    "        new = self._Node(e,pred,succ)\n",
    "        pred._next=new\n",
    "        succ._prev=new\n",
    "        self._size+=1\n",
    "        return new\n",
    "    \n",
    "    def _delete(self,node):\n",
    "        pred=node._prev\n",
    "        succ=node._next\n",
    "        pred._next=succ\n",
    "        succ._prev=pred\n",
    "        self._size-=1\n",
    "        elem=node._elem\n",
    "        node._prev=node._next=node._elem=None\n",
    "        return elem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Problem 5-2\n",
    "class Tree(object):\n",
    "    class Position(object):\n",
    "        def element(self):\n",
    "            raise NotImplementedError('must implemented by subclass')\n",
    "            \n",
    "        def __eq__(self,other):\n",
    "            raise NotImplementedError('must implemented by subclass')\n",
    "            \n",
    "        def __neq__(self,other):\n",
    "            return not (self==other)\n",
    "    \n",
    "    def root(self):\n",
    "        raise NotImplementedError('must implemented by subclass')\n",
    "\n",
    "    def children(self,p):\n",
    "        raise NotImplementedError('must implemented by subclass')\n",
    "\n",
    "    def is_empty(self):\n",
    "        return len(self) == 0\n",
    "\n",
    "    def breadthfirst(self):\n",
    "        if not self.is_empty():\n",
    "            Q=LinkedQueue()\n",
    "            Q.enqueue(self.root())\n",
    "            while not Q.is_empty():\n",
    "                p=Q.dequeue()\n",
    "                yield p\n",
    "                for c in self.children(p):\n",
    "                    Q.enqueue(c)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
